#pragma once

#include <vector>
#include <stack>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include "Generators.h"

#include "StronglyConnectedComponentsGraph.h"



class simpleDfsClass{
private:
	std::vector<int> onPathVertexes_;
public:
	void beforeStep(int startVertex){
	}

	void beforeWhiteVertex(int vertex, int parent){
		onPathVertexes_.push_back(vertex);
	}

	void beforeGreyVertex(int toVertex, int fromVertex){

	}
	void beforeBlackVertex(int toVertex, int fromVertex){

	}

	void afterCurrentStep(int vertex, int parent){

	}

	void afterOverallStep(){}

	std::vector<int> afterDFS(){
		return onPathVertexes_;
	}
	void clearData(){
		onPathVertexes_.clear();
	}
};



void trivialTarjanCheck(Graph &G, const std::vector<int>& componentsList){
	std::vector<colors> vertexColors(G.getVertexNum(), WHITE);
	std::stack<int> vertexStack;
	std::vector<std::vector<int> > adjacentList(G.getVertexNum());
	std::vector<std::vector<int>::iterator > iteratorList(G.getVertexNum());
	std::vector<int> parentsList(G.getVertexNum());
	std::vector<std::vector<bool> > linkBetweenVertexes(G.getVertexNum(), std::vector<bool>(G.getVertexNum(), false));

	simpleDfsClass currentUserClass;
	for (int currentVertex = 0; currentVertex < G.getVertexNum(); ++currentVertex){
		vertexColors.assign(G.getVertexNum(), WHITE);
		vertexStack.push(currentVertex);
		currentUserClass.clearData();
		DFSStep(G, &currentUserClass, &vertexStack, &vertexColors, &adjacentList,
			&iteratorList, &parentsList, currentVertex);
		std::vector<int> reachebleList = currentUserClass.afterDFS();
		for (auto toVertex : reachebleList){
			linkBetweenVertexes[currentVertex][toVertex] = true;
		}
	}
	for (int firstVertex = 0; firstVertex < G.getVertexNum(); ++firstVertex){
		for (int secondVertex = 0; secondVertex < G.getVertexNum(); ++secondVertex){
			if (linkBetweenVertexes[firstVertex][secondVertex] && linkBetweenVertexes[secondVertex][firstVertex] &&
				(componentsList[firstVertex] != componentsList[secondVertex])){
				throw std::logic_error("Wrong finding strongly components");
			}
		}
	}
}


void stressRandomTarjanCheck(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		Graph G;
		generateGraph(G);
		StronglyComponentsFindClass tarjanClass(G.getVertexNum());
		DFS(G, &tarjanClass);
		std::vector<int> componentsList = tarjanClass.afterDFS();
		trivialTarjanCheck(G, componentsList);
	}
}

std::vector<int> getMaskArray(int mask, int maskSize){
	std::vector<int> maskArray(maskSize);
	for (int currentPosition = 0; currentPosition < maskSize; ++currentPosition){
		maskArray.push_back(mask % 3);
		mask /= 3;
	}
	return maskArray;
}
void stressAllSmallGraphs(){
	for (int vertexNum = 1; vertexNum <= 6; ++vertexNum){
		int overallMasksCount = pow(3, vertexNum*(vertexNum - 1) / 2) + 0.01;
		for (int currentMask = 0; currentMask < overallMasksCount; ++currentMask){
			Graph G;
			std::vector<std::pair<int, int > > edgesList;
			std::vector<int> maskArray = getMaskArray(currentMask, vertexNum*(vertexNum - 1) / 2);
			int positionInMask = 0;
			for (int firstVertex = 0; firstVertex < vertexNum; ++firstVertex){
				for (int secondVertex = firstVertex + 1; secondVertex < vertexNum; ++secondVertex){
					if (maskArray[positionInMask] == 1){
						edgesList.push_back({ firstVertex, secondVertex });
					}
					else if (maskArray[positionInMask] == 2){
						edgesList.push_back({ secondVertex, firstVertex });
					}
					positionInMask++;
				}
			}
			G.readGraph(vertexNum, (int)edgesList.size(), edgesList);
			StronglyComponentsFindClass componentClass(vertexNum);
			DFS(G, &componentClass);
			std::vector<int> componentsList = componentClass.afterDFS();
			trivialTarjanCheck(G, componentsList);
		}
	}
}

void stressRandomShuffleTests(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		int vertexNum;
		std::vector<std::pair<int, int> >edgesList;
		generateScriptForGraph(vertexNum, edgesList);
		Graph G;
		G.readGraph(vertexNum, (int)edgesList.size(), edgesList);
		std::vector<int> permutation(vertexNum);
		for (int position = 0; position < vertexNum; ++position){
			permutation[position] = position;
		}
		std::random_shuffle(permutation.begin(), permutation.end());
		for (size_t currentEdge = 0; currentEdge < (int)edgesList.size(); ++currentEdge){
			edgesList[currentEdge].first = permutation[edgesList[currentEdge].first];
			edgesList[currentEdge].second = permutation[edgesList[currentEdge].second];
		}
		std::random_shuffle(edgesList.begin(), edgesList.end());
		Graph permutationGraph;
		permutationGraph.readGraph(vertexNum, (int)edgesList.size(), edgesList);
		StronglyComponentsFindClass componentsForGraph(vertexNum), componentsForPermutationGraph(vertexNum);
		DFS(G, &componentsForGraph);
		DFS(permutationGraph, &componentsForPermutationGraph);
		std::vector<int> componentsList = componentsForGraph.afterDFS();
		std::vector<int> componentsListPermutation = componentsForPermutationGraph.afterDFS();
		for (int firstVertex = 0; firstVertex < vertexNum; ++firstVertex){
			for (int secondVertex = firstVertex + 1; secondVertex < vertexNum; ++secondVertex){
				if ((componentsList[firstVertex] == componentsList[secondVertex]) !=
					(componentsListPermutation[permutation[firstVertex]]
					== componentsListPermutation[permutation[secondVertex]])){
					throw std::logic_error("Components search depends on order of vertexes");
				}
			}
		}
	}
}

